// Learn TypeScript:
//  - https://docs.cocos.com/creator/manual/en/scripting/typescript.html
// Learn Attribute:
//  - https://docs.cocos.com/creator/manual/en/scripting/reference/attributes.html
// Learn life-cycle callbacks:
//  - https://docs.cocos.com/creator/manual/en/scripting/life-cycle-callbacks.html


/**
 * 1、使用深度优先算法随机一条路径，存储在pathArray中。
 * 2、如果路径走到头回溯到另一个点上。pathArray中根据回溯到的点判断，删除无效路径点。（具体判断逻辑: 点上具备方向从而得出该回溯点从哪个方向加入）
 * 3、重复上述知道找到目标点。
 */
const { ccclass, property } = cc._decorator;

@ccclass
export default class DepthFirstSearch extends cc.Component {

    private mapData: Array<number>[] = new Array(); //二维数组0代表无访问1代表已经访问
    private mapSign: Array<boolean>[] = new Array();//状态标记：true加入准备访问状态/false未加入准备访问状态
    private pathArray: cc.Vec2[] = []; //存储一条随机路径
    private isEndOf: boolean = true; //一条路走到尽头的标志

    private row_h: number = 5;
    private row_v: number = 5;
    onLoad() { }

    start() {
        //初始化数组
        for (let i = 0; i < this.row_h; i++) {
            this.mapData[i] = new Array();
            this.mapSign[i] = new Array();
            for (let j = 0; j < this.row_v; j++) {
                this.mapData[i][j] = 0; //初始状态
                this.mapSign[i][j] = false; //初始状态
            }
        }
        let s_point: cc.Vec2 = cc.v2(0, 0); //开始点
        let e_point: cc.Vec2 = cc.v2(3, 3); //结束点
        //开始进入深度搜索
        this.depthFirstSearch(s_point, e_point);

        //输出结果
        cc.warn("****输出走过的所有路线(包含回溯)****")
        for (let i = 0; i < this.row_h; i++) {
            cc.error(this.mapData[i].toString());
            cc.log("\n")
        }
        cc.warn("********输出随机的这条路线)********")
        for (let i = 0; i < this.pathArray.length; i++) {
            let x = this.pathArray[i].x;
            let y = this.pathArray[i].y;
            this.mapData[x][y] = 8;
        }
        for (let i = 0; i < this.row_h; i++) {
            cc.error(this.mapData[i].toString());
            cc.log("\n")
        }
    }

    private depthFirstSearch(s_point: cc.Vec2, e_point: cc.Vec2): void {
        if (s_point.x < 0 || s_point.x >= this.row_h || s_point.y < 0 || s_point.y >= this.row_v) {
            cc.log("起始点越界")
            return;
        }
        if (e_point.x < 0 || e_point.x >= this.row_h || e_point.y < 0 || e_point.y >= this.row_v) {
            cc.log("目标点越界")
            return;
        }
        //方向随机
        let randArray: string[] = ['up', 'down', 'left', 'right'];
        let _length = randArray.length;
        //初始化栈结构
        let stack: object[] = [];
        let tempData: any = { c_point: s_point, dir: 'null' };
        stack.push(tempData);
        while (stack.length != 0) {
            let _tempData: any = stack.pop();
            let x = _tempData.c_point.x;
            let y = _tempData.c_point.y;
            this.mapData[x][y] = 1;   //标记状态已经访问
            this.mapSign[x][y] = true;//标记状态准备访问
            this.pathArray.push(cc.v2(x, y));
            if (x == e_point.x && y == e_point.y) { return; } //gameOver

            this.isEndOf = true;
            //随机遍历上下左右方向
            //深度优先级算法中存在回溯问题
            for (let i = 0, j = randArray.length; i < j; i++) {
                let rand: string = this.getRandom(randArray, _length); //不重复随机方向
                if (_length <= 1) { _length = randArray.length; }
                else { _length--; }
                let tempPoint: cc.Vec2 = null;
                if (rand == 'up' && x - 1 > 0) {
                    tempPoint = cc.v2(x - 1, y);
                    this.dirSearch(stack, tempPoint, rand);
                }
                else if (rand == 'down' && x + 1 < this.row_h) {
                    tempPoint = cc.v2(x + 1, y);
                    this.dirSearch(stack, tempPoint, rand);
                }
                else if (rand == 'left' && y - 1 >= 0) {
                    tempPoint = cc.v2(x, y - 1);
                    this.dirSearch(stack, tempPoint, rand);
                }
                else if (rand == 'right' && y + 1 < this.row_v) {
                    tempPoint = cc.v2(x, y + 1);
                    this.dirSearch(stack, tempPoint, rand);
                }
            }

            //解决回溯过程产生的无效点路径
            if (this.isEndOf) {
                cc.error("*************进入处理回溯问题*************")
                let _tempData: any = stack[stack.length - 1];
                if (_tempData) {
                    let dir: string = _tempData.dir;
                    let c_point: cc.Vec2 = _tempData.c_point;
                    let point: cc.Vec2 = cc.v2(0, 0);
                    if (dir == 'up') {
                        point = cc.v2(c_point.x + 1, c_point.y)
                    }
                    else if (dir == 'down') {
                        point = cc.v2(c_point.x - 1, c_point.y);
                    }
                    else if (dir == 'left') {
                        point = cc.v2(c_point.x, c_point.y + 1);
                    }
                    else if (dir == 'right') {
                        point = cc.v2(c_point.x, c_point.y - 1);
                    }

                    for (let i = 0, j = this.pathArray.length; i < j; i++) {
                        let x = this.pathArray[i].x;
                        let y = this.pathArray[i].y;
                        if (x == point.x && y == point.y) {
                            this.pathArray.length = i + 1;//删除无效路径
                            break;
                        }
                    }
                }
            }
        }
    }

    private getRandom(arr: Array<string>, curLen: number): string {
        let index = Math.floor(Math.random() * curLen);
        let temp = arr[index];
        arr[index] = arr[curLen - 1];
        arr[curLen - 1] = temp;
        return temp;
    }

    private dirSearch(stack: object[], tempPoint: cc.Vec2, rand: string): void {
        if (this.mapData[tempPoint.x][tempPoint.y] == 0 && this.mapSign[tempPoint.x][tempPoint.y] == false) { //如果要设置障碍物。this.mapData[tempPoint.x][tempPoint.y] ！= 0
            this.mapSign[tempPoint.x][tempPoint.y] = true;
            let _tempData: any = { c_point: tempPoint, dir: rand };
            stack.push(_tempData);
            this.isEndOf = false;
        }
    }
}
